package com.cat.dataStructure03;

import java.util.Arrays;

class Solution28 {
    int[][][] dp;
    int[][] g;
    int dfs(int x, int y, int k) {
        if (x < 0 || y < 0 || k < 0) {
            return Integer.MIN_VALUE;
        }
        if (x == 0 && y == 0) {
            return 0;
        }
        if (dp[x][y][k] != -1) {
            return dp[x][y][k];
        }
        int newK = k;
        if (g[x][y] != 0) {
            newK--;
        }
        return dp[x][y][k] = Math.max(dfs(x - 1, y, newK), dfs(x, y - 1, newK)) + g[x][y];
    }
    public int maxPathScore(int[][] grid, int k) {
        int n = grid.length, m = grid[0].length;
        dp = new int[n][m][k + 1];
        g = grid;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        int ans = dfs(n - 1, m - 1, k);
        return ans < 0 ? -1 : ans;
    }
}